//
// Created by PC on 2023-9-1
// 二进制数相加
// https://leetcode.cn/problems/add-binary/submissions/
// 1 <= a.length, b.length <= 10^4
// 通过 直接计算 判断是否进位 时间8ms和内存9.20MB均不理想


#include <iostream>
#include <string>
#include <cmath>

using namespace std;

string addBinary(string a, string b)
{
    if (a=="0" && b=="0")
        return "0";
    int al = a.size();
    int bl = b.size();
    // 让两个字符串长度相等, 短的前边补"0"
    while(al>bl)
    {
        b="0"+b;
        ++bl;
    }
    while(bl>al)
    {
        a="0"+a;
        ++al;
    }
    bool carry = false;
    string ans;
    for(int i=al-1; i>=0;--i)
    {
        char ai=a[i],bi=b[i];
        if (carry)
        {
            if (ai=='1' && bi=='1')
            {
                carry = true;
                ans="1"+ans; // 从左往右添加字符串
            } else if (ai=='0' && bi=='0')
            {
                carry = false;
                ans = "1"+ans;
            } else{
                carry = true;
                ans = "0"+ans;
            }
        }
        // 没有进位
        else{
            if (ai=='1' && bi=='1')
            {
                carry = true;
                ans="0"+ans; // 从左往右添加字符串
            } else if (ai=='0' && bi=='0')
            {
                carry = false;
                ans = "0"+ans;
            } else{
                carry = false;
                ans = "1"+ans;
            }
        }
    }
    if (carry)
        ans = "1"+ans;
//    cout<<a<<' '<<al<<endl;
//    cout<<b<<' '<<bl<<endl;
    return ans;
}

int main()
{
    string a = "1111001", b = "1001001";
    a="11",b="10";
//    a="0",b="0";
    cout<<addBinary(a,b);
    return 0;
}